package basis.netease.medium;

import java.util.LinkedList;
import java.util.Scanner;

/**
 * 7-3 删除无效的括号
 * 给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
 * 括号只考虑 "(" 和 ")" ，有效的括号是指一系列左括号 "(" 和 ")" 组成；但是如果有一些额外的括号，使得括号不能正确配对，就需要删除。
 * 删除规则：从前往后，且尽可能少的删除多余括号。
 * 输入格式:
 * 输入一个字符串，字符串的长度小于1000。字符串中只包含字母、 "(" 和 ")"
 * 输出格式:
 * 输出处理后的字符串
 * 输入样例:
 * 在这里给出一组输入。例如：
 * a)())()
 * 输出样例:
 * 在这里给出相应的输出。例如：
 * a()()
 */
public class Main_3 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        // 只存左括号的索引，用于给右括号进行匹配
        LinkedList<Integer> stack = new LinkedList();
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (c == '(') {
                stack.push(i);
            } else if (c == ')') {
                // stack中无值，匹配失败，直接从字符串移除右括号；stack中有值，匹配成功
                if (stack.isEmpty()) {
                    input = input.substring(0, i) + input.substring(i + 1);
                    i--;
                } else {
                    stack.pop();
                }
            }
        }
        // 删除未匹配的左括号
        while (!stack.isEmpty()) {
            int i = stack.pop();
            input = input.substring(0, i) + input.substring(i + 1);
        }
        System.out.println(input);
    }

}
